package com.mgq.algorithm.dabiaofa;

/**
 * 吃草问题,有A和B
 * 每次只能吃4的n次方的草.给一个n,返回最终谁会赢,每次都得吃
 */
public class EatGrass {
    /**
     * @param n
     * @return 先手 or 后手
     */
    public static String process(int n) {
        if (n < 5) {
            //0  1  2  3  4
            //后 先  后 先 先
            if (n == 0 || n == 2) {
                return "后手";
            } else {
                return "先手";
            }
        }
        int base = 1;
        while (base <= n) {
            if (process(n - base).equals("后手")) {
                return "先手";
            }
            //提前判断,防止溢出
            if (base > n / 4) { //防止溢出
                break;
            }
            base = base * 4;
        }
        return "后手";

    }

    /**
     * n=5 后手
     * n=6 先手
     * n=7 后手
     * n=8 先手
     * n=9 先手
     * n=10 后手
     * n=11 先手
     * n=12 后手
     * n=13 先手
     * n=14 先手
     * @param n
     * @return 规律就是 后 先 后 先 先
     */
    public static String process2(int n) {
        if (n % 5 == 0 || n % 5 == 2) {
            return "后手";
        } else {
            return "先手";
        }
    }
    public static void main(String[] args) {
        for (int i = 0; i < 50; i++) {
            //System.out.println(process(i)==process2(i));
            System.out.println("n="+i+" "+process(i));
        }

       /* System.out.println(Math.pow(4,0));
        System.out.println(Math.pow(4,1));
        System.out.println(Math.pow(4,2));*/
    }
}
